#include "stack_queue.h"
#include <iostream>
#include <string>
#include <vector>
using namespace std;

/*================================= 节点 =====================================*/
listNode::listNode() : next(NULL), data(0) {}

listNode::listNode(int nodeData, listNode* succ) : next(succ), data(nodeData) {}

listNode::~listNode() {}

/*================================= 栈实现 ====================================*/
MyStack::MyStack() {
    topNode = NULL;
    stackSize = 0;
}

MyStack::~MyStack() {
    while (topNode != NULL) {
        listNode* p = topNode;
        topNode = topNode->next;
        delete p;
    }
    stackSize = 0;
}

bool MyStack::push(const int& elem) {
    listNode* p = new listNode(elem, topNode);
    topNode = p;
    stackSize++;
    return true;
}

bool MyStack::pop(int& item) {
    if (stackSize == 0 || topNode == NULL) {
        return false;
    }
    listNode* p = topNode;
    item = p->data;
    topNode = p->next;
    delete p;
    stackSize--;
    return true;
}

bool MyStack::getTop(int& item) {
    if (stackSize == 0 || topNode == NULL) {
        return false;
    }
    item = topNode->data;
    return true;
}

void MyStack::printStack() {
    listNode* p = topNode;

    while (p != NULL) {
        if (p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;

    }
}

bool MyStack::isEmpty() const {
    return stackSize == 0;
}

/*============================ 队列实现 ============================*/
MyQueue::MyQueue(const int& capacity) {
    if (capacity <= 0) {
        throw invalid_argument("容量必须为正整数");
    }
    this->capacity = capacity;
    queue = new int[capacity];
    front = 0;
    rear = 0;
}

MyQueue::MyQueue(const MyQueue& other) {
    capacity = other.capacity;
    front = other.front;
    rear = other.rear;
    queue = new int[capacity]; 
    int size = (rear - front + capacity) % capacity;
    for (int i = 0; i < size; i++) {
        int idx = (front + i) % capacity;
        queue[idx] = other.queue[idx];
    }
}

MyQueue& MyQueue::operator=(const MyQueue& other) {
    if (this == &other) return *this;
    delete[] queue;
    capacity = other.capacity;
    front = other.front;
    rear = other.rear;
    queue = new int[capacity];
    int size = (rear - front + capacity) % capacity;
    for (int i = 0; i < size; i++) {
        int idx = (front + i) % capacity;
        queue[idx] = other.queue[idx];
    }
    return *this;
}

MyQueue::~MyQueue() {
    delete[] queue;
}

bool MyQueue::enQueue(const int& elem) {
    if (isFull()) {
        return false;
    }
    queue[rear % capacity] = elem;
    rear = (rear + 1) % capacity;
    return true;
}

bool MyQueue::deQueue(int& item) {
    if (isEmpty()) {
        return false;
    }
    item = queue[front % capacity];
    front = (front + 1) % capacity;
    return true;
}

bool MyQueue::getFront(int& item) {
    if (isEmpty()) {
        return false;
    }
    item = queue[front % capacity];
    return true;
}

void MyQueue::printQueue() {
    int cursor = front;

    while (cursor != rear)
    {
        if ((cursor + 1) % capacity == rear)
            cout << queue[cursor] << endl;
        else
            cout << queue[cursor] << ",";

        cursor = (cursor + 1) % capacity;
    }
}

bool MyQueue::isEmpty() {
    return front == rear;
}

bool MyQueue::isFull() {
    return ((rear + 1) % capacity) == front;
}

/*============================= 表达式相关 ==============================*/
static int getPriority(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

bool postfixExpression(const string& middle, string& result) {
    MyStack s;
    result.clear();
    for (int i = 0; i < middle.length(); i++) {
        int ch = middle.at(i);
        if (ch >= '0' && ch <= '9') {
            result.push_back(ch);
        }
        else if (ch == '(') {
            s.push(ch);
        }
        else if (ch == ')') {
            int temp;
            bool check = false;
            while (s.getTop(temp)) {
                if (temp == '(') {
                    check = true;
                    s.pop(temp);
                    break;
                }
                else {
                    result.push_back(temp);
                    s.pop(temp);
                }
            }
            if (!check) {
                result = "Expression is wrong!";
                return false;
            }
        }
        else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
            int temp2;
            while (s.getTop(temp2)&&temp2!='('&& getPriority(temp2) >= getPriority(ch)) {
                result.push_back(temp2);
                s.pop(temp2);
            }
            s.push(ch);
        }
        else {
            result = "Expression is wrong!";
            return false;
        }
    }
    int temp3;
    while (s.getTop(temp3)) {
        if (temp3 == '(' || temp3 == ')') {
            result = "Expression is wrong!";
            return false;
        }
        result += temp3;
        s.pop(temp3);
    }
    return true;
}

bool expressionVal(const string& middle, int& value) {
    string last = "";
    postfixExpression(middle, last);
    MyStack s;
    for (size_t i = 0; i < last.length(); ++i) {
        char ch = last.at(i);
        if (ch == ' ') continue;
        if (ch >= '0' && ch <= '9') {
            s.push(int(ch - '0'));
        } else {
            int rhs, lhs;
            if (!s.pop(rhs) || !s.pop(lhs)) return false;
            long long res = 0;
            switch (ch) {
            case '+': res = lhs + rhs; break;
            case '-': res = lhs - rhs; break;
            case '*': res = lhs * rhs; break;
            case '/': if (rhs == 0) return false; res = lhs / rhs; break;
            default: return false;
            }
            s.push(int(res));
        }
    }
    int out;
    if (!s.pop(out)) return false;
    if (!s.isEmpty()) return false;
    value = out;
    return true;
}

/*============================= 杨辉三角 ==============================*/
void yanghui(const int& n) {
    if (n <= 0) return;
    MyQueue q(n + 2); 
    q.enQueue(1);
    q.enQueue(1);
    for (int i = 1; i <= n; i++) { 
        int size = (q.rear - q.front + q.capacity) % q.capacity;
        int* arr = new int[size];
        int cursor = q.front;
        for (int j = 0; j < size; j++) {
            arr[j] = q.queue[cursor];
            cout << arr[j];
            if (j < size - 1) cout << ",";
            cursor = (cursor + 1) % q.capacity;
        }
        cout << endl;
        if (i < n) { 
            MyQueue nextq(q.capacity + 1); 
            int pre = 0; 
            for (int j = 0; j < size; j++) {
                int current = arr[j];
                nextq.enQueue(pre + current); 
                pre = current;
            }
            nextq.enQueue(pre); 
            q = nextq; 
        }
        delete[] arr;
    }
}


